/**
 * This file is part of Graph-Tool.
 * 
 * Graph-Tool is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
 * Graph-Tool is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * Graph-Tool. If not, see <http://www.gnu.org/licenses/>.
 */
package graphtool.graphs.algorithms.undirected;

import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Vector;

import graphtool.graphs.Pair;
import graphtool.graphs.UndirectedGraph;
import graphtool.graphs.algorithms.AlgorithmException;

/**
 * @author a.lunkeit - alunkeit(at)gmail(dot)com
 * 
 *         An implementation of the Kruskal algorithm. It can be used for
 *         finding a minimum spanning tree of an undirected connected graph.
 * 
 */
public final class Kruskal<V, E> implements Comparator<Pair<Float, E>>
{

  UndirectedGraph<V, E> _graph;

  Collection<Pair<Float, E>> _weightedEdges = new Vector<Pair<Float, E>>();

  Collection<E> _spanningEdges = new Vector<E>();

  /**
   * Constructor
   */
  public Kruskal( UndirectedGraph<V, E> graph ) throws AlgorithmException
  {
    if( null == graph )
    {
      throw new AlgorithmException( "Algorithm not applicable for null objects" );
    }

    _graph = graph;

    initialize();

    try
    {
      kruskal();
    }
    catch( Exception e )
    {
      e.printStackTrace();
    }
  }

  /**
   * Internal routine for initialization
   */
  private void initialize()
  {
    Iterator<E> eIter = _graph.getEdges().iterator();

    while( eIter.hasNext() )
    {
      E e = eIter.next();

      float weight = _graph.getEdgeWeight( e );

      Pair<Float, E> p = new Pair<Float, E>();
      p.setKey( weight );
      p.setValue( e );

      _weightedEdges.add( p );
    }
  }

  /**
   * The implementation of Kruskals algorithm. It set's up a priority queue from
   * the edges in the graph and iterates through them. Starting with the edge
   * having the smallest weight the algorithm adds the next edge in case that it
   * will no create a circle with the edges already added to the result set.
   */
  private void kruskal() throws Exception
  {
    // Step 1: Make an priority queue and order the edges due to their weight.
    PriorityQueue<Pair<Float, E>> queue = new PriorityQueue<Pair<Float, E>>( _weightedEdges.size(), this );

    Iterator<Pair<Float, E>> wIter = _weightedEdges.iterator();

    while( wIter.hasNext() )
    {
      queue.add( wIter.next() );
    }

    Pair<Float, E> p = null;

    Vector<V> vertices = new Vector<V>();

    while( (p = queue.poll()) != null )
    {

      E edge = p.getValue();
      Pair<V, V> vp = _graph.getEndpoints( p.getValue() );

      if( vertices.contains( vp.getKey() ) && vertices.contains( vp.getValue() ) )
      {
        continue;
      }
      else
      {
        _spanningEdges.add( edge );
        vertices.add( vp.getKey() );
        vertices.add( vp.getValue() );
      }

    }
  }

  /*
   * (non-Javadoc)
   * 
   * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
   */
  @Override
  public int compare( Pair<Float, E> o1, Pair<Float, E> o2 )
  {
    if( o1.getKey().floatValue() < o2.getKey().floatValue() )
      return -1;

    else if( o1.getKey().floatValue() == o2.getKey().floatValue() )
      return 0;

    else
      return 1;
  }
  
  /**
   * Returns the result set containing the spanning tree edges.
   * 
   * @return
   */
  public Collection<E> getSpanningTreeEdges()
  {
    return _spanningEdges;
  }
}
